package al234isPalindrome;

import al206reverseList.ReverseList;

import java.util.List;
import java.util.Stack;

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}


public class IsPalindrome234 {

/*    反转并比较
    public static boolean isPalindrome(ListNode head) {
        // 创建一个新的头节点
        ListNode newHead = new ListNode(head.val);
        ListNode current = head.next;
        ListNode newCurrent = newHead;

        // 遍历原链表并复制每个节点
        while (current != null) {
            newCurrent.next = new ListNode(current.val); // 创建新节点并连接
            newCurrent = newCurrent.next; // 移动到新链表的末尾
            current = current.next; // 移动到原链表的下一个节点
        }
        ListNode p = newHead;

        ListNode reverseList = reverseList(head);
        ListNode rp = reverseList;
        while (p!=null){
            if(p.val!=rp.val){
                return false;
            }
            p = p.next;
            rp = rp.next;
        }
        return true;
    }*/

    public static ListNode reverseList(ListNode head) {
        ListNode listNode = new ListNode();
        if (head==null || head.next==null) {
            return head;
        }
        ListNode pre = null;
        ListNode cur = head;
        ListNode after = head.next;

        while (after!=null){
            cur.next = pre;
            pre = cur;
            cur = after;
            after = after.next;
        }
        cur.next=pre;
        pre = cur;
        return pre;
    }

/* 暴力法找中间节点
   public static boolean isPalindrome(ListNode head) {

        int len = 0;
        ListNode p = head;
        if (p==null || p.next ==null){
            return true;
        }
        while (p != null) {
            p = p.next;
            len++;
        }
        len = len/2;
        int temp = 1;
        ListNode rp = null;
        ListNode rList = null;
        p = head;
        while (p!=null){
            if (temp==len){
                rp = p.next;
                p.next=null;
                rList = reverseList(rp);
                break;
            }
            p=p.next;
            temp++;
        }

        p = head;
        while (p!=null){
            if (p.val!=rList.val){
                return false;
            }
            p=p.next;
            rList=rList.next;
        }

        return true;
    }*/

    public static boolean isPalindrome(ListNode head) {

        ListNode p = head;
        if (p==null || p.next ==null){
            return true;
        }
        ListNode pa = head.next;

        while (pa.next != null && pa.next.next!=null) {
            p = p.next;
            pa= pa.next.next;
        }
        ListNode rList = reverseList(p.next);
        p = head;
        while (rList!=null){
            if (rList.val != p.val) {
                return false;
            }
            rList =rList.next;
            p = p.next;
        }
        return true;
    }
    public static void main(String[] args) {
        // 创建一个链表：1 -> 2 -> 3 -> 4 -> 5
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(3);
        head.next.next.next.next = new ListNode(0);
        head.next.next.next.next.next = new ListNode(1);

        boolean palindrome = isPalindrome(head);
        System.out.println(palindrome);
    }
}
